เราสามารถอธิบายเส้นใยที่มองไม่เห็นซึ่งเชื่อมโยงสังคมอย่างเป็นระบบทางคณิตศาสตร์ได้อย่างไร? ไม่ว่าจะเป็น เลขเบคอน ที่เชื่อมโยงเบลา ลูโกซีกับดาราฮอลลีวูด หรือ กราฟความคล้ายคลึงกัน การจัดกลุ่มจุดข้อมูลตามระยะห่างใกล้เคียงกัน, ทฤษฎีกราฟ ให้ภาษาทางคณิตศาสตร์รูปแบบหนึ่งคือ $G = (V, E)$ เพื่อสร้างแบบจำลองของจักรวาลที่แยกจากกันเหล่านี้
1. โครงสร้างของกราฟ
ในหลักการพื้นฐาน กราฟประกอบด้วยเซตของ จุดยอด ($V$) และเซตของ เส้นเชื่อม ($E$) อย่างไรก็ตาม กฎของการใช้งานจะแตกต่างกันตามโครงสร้าง:
- กราฟแบบง่าย: รูปแบบที่เรียบง่ายที่สุด; มันห้าม วงวน (เส้นเชื่อมที่เชื่อมจุดยอดกับตัวเอง) และ เส้นเชื่อมขนาน (เส้นเชื่อมที่ซ้ำซ้อนระหว่างจุดสองจุดเดียวกัน)
- กราฟหลายเส้น: อนุญาตให้มีวงวนและเส้นเชื่อมขนาน มักใช้ในการจำลองการมีปฏิสัมพันธ์หลายประเภท เช่น การส่งข้อความเทียบกับการโทร ระหว่างโหนดเดียวกัน
- จุดยอดที่แยกตัว: จุดยอด $v$ จะถือว่าเป็นจุดยอดที่แยกตัว หากไม่มีเส้นเชื่อมใดๆ ผ่านมัน ซึ่งแสดงถึงวัตถุที่ไม่มีความสัมพันธ์ใดๆ ในชุดปัจจุบัน
ในงานวิทยาศาสตร์ข้อมูล เราจะใช้ ฟังก์ชันความไม่คล้ายกัน เพื่อสร้างกราฟ:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
เราจะวาดเส้นเชื่อมระหว่าง $v$ กับ $w$ ก็ต่อเมื่อ $s(v, w)$ ต่ำกว่าเกณฑ์ที่กำหนด ซึ่งช่วยสร้างเครือข่ายของ 'เพื่อนบ้าน' ได้อย่างมีประสิทธิภาพ
2. เส้นทาง ความเชื่อมต่อ และองค์ประกอบ
เส้นทาง เส้นทาง คือลำดับของจุดยอดและเส้นเชื่อม หากเส้นทางนั้นไม่ไปเยี่ยมชมจุดยอดใดซ้ำมากกว่าหนึ่งครั้ง จะถือว่าเป็น เส้นทางแบบง่าย. ความเชื่อมต่อคือหัวใจของกราฟ:
- กราฟที่เชื่อมต่อ: มีเส้นทางระหว่าง ทุก คู่ของจุดยอดทุกคู่ในกราฟ
- องค์ประกอบ: หากกราฟไม่เชื่อมต่อ มันจะแบ่งออกเป็นชิ้นส่วนที่แยกจากกันเรียกว่าองค์ประกอบ แต่ละองค์ประกอบเป็นกราฟย่อยที่เชื่อมต่ออย่างสูงสุด
3. กราฟย่อย: สถาปัตยกรรมของเซตย่อย
กราฟย่อย $G' = (V', E')$ เป็นเซตย่อยของกราฟ $G$ โดยที่จุดยอดทุกจุดใน $V'$ ต้องมีอยู่ใน $V$ และเส้นเชื่อมทุกเส้นใน $E'$ ต้องเชื่อมจุดยอดที่พบใน $V'$ ซึ่งการระบุกราฟย่อยมีความสำคัญต่อการตรวจจับรูปแบบเฉพาะเจาะจงภายในเครือข่ายทั้งหมด